1. Field of the Invention
This invention relates to the field of locking data structures in a multi-threaded computing environment. Specifically, this invention is a method, apparatus, and computer program product for locking interrelated groups of data structures in a multi-threaded computing environment.
2. Background
Data structures contain organized information in a computer's memory. Each of these data structures can be independent or interrelated to other data structures. Access to the data structures is simple when the access occurs in a computing environment that has a single flow of execution (thread-of-execution) because the data in the interrelated data structures is always consistent during the execution of the single thread. However, if an asynchronous operation occurs (such as an interrupt, process context switch or similar operation that allows for concurrent access to the data structure) the contents of the data structure may be made inconsistent if an asynchronous operation changes the data structure while another operation is accessing the data structure. Modem computing systems often use threads-of-execution to parallelize computer operations.
A thread-of-execution (a thread) is a sequence of control within a programmed-process. A traditional single-threaded programmed-process follows a single sequence-of-control while executing. A multithreaded programmed-process has several sequences of control, and is capable of several independent actions. A particular implementation of a multi-threaded computing environment is discussed in SunOS Multi-thread Architecture, by Powell, Kleiman, Barton, Shah, Stein and Weeks, USENIX, Winter 1991, page 65. Posie.RTM. threads are described in Programming with POSIX Threads, by David R. Butenhof, .COPYRGT. 1997 by Addison Wesley Longman, Inc., ISBN 0-201-63392-2, pages 35-95.
The subsequently disclosed invention is described within the context of an object-oriented programming (OOP) paradigm. The OOP paradigm uses objects. Objects associate an object's data with OOP methods for operating on that object's data Usually, OOP objects are instantiated in a heap memory area and are based on classes that reference the programmed methods for the OOP object. Instantiated OOP objects are accessed through pointers and contain data (in instance variables) specific to that particular instantiated OOP object. Conceptually, an OOP object contains object-related information (such as the number of instance variables in the object), data structures for storing the object's instance variables, and addresses of called-routines (OOP methods) that access and/or manipulate the contents of the instance variables in the object. However, because objects often share called-routines and object-related information, this shared information is usually extracted into a class. Thus, the instantiated object simply contains its instance variables and a pointer to its class. Further information about OOP concepts may be found in Not Just Java by Peter van der Linden, Sun Microsystems Press/Prentice Hall PTR Corp., Upper Saddle River, N.J., (1997), ISBN 0-13-864638-4, pages 136-149.
Data structures also can be treated as objects within the OOP paradigm. Such data structure objects include the instantiated data that make up the data structure, programmed methods to access this data and potentially links to other data structure objects.
A useful data structure for image processing purposes (and many other purposes) is a modified directed acyclic graph (DAG) that represents images and the operations applied to these images. The DAG elements can be represented as objects. One or more DAGs can be constructed by an imaging library as the library captures a series of imaging operations directed to one or more source images. The resulting DAGs are contained within an object collection. The object collection generally contains both independent and interrelated DAG objects. Independent objects are those that do not depend on other objects. Interrelated objects access each other to perform their operation. An independent object can be locked by a thread to assure exclusive access to the thread. However, to lock an interrelated object, each interrelated object must also be locked to assure that the information in the object is not changed by a second thread while a first thread is processing
One prior art approach to locking objects uses a mutex to serialize thread access to the object collection. The difficulty with this approach is that while one thread processes objects in the object collection other threads cannot. Thus, independent operations, controlled by threads, that need to access an object in the object collection cannot make the access until the locking thread releases the object collection. This approach limits the advantages of a multithreaded computing environment by making the object collection a blocking resource.
Another prior art approach assigns a mutex (generally within a control object) to serialize access to each group of objects that may be interrelated in the object collection. Thus, the object collection may have multiple control-objects each controlling access to an independent group of the object collection where each group contains objects that may be interdependent. The difficulty with this prior art approach is that the control-object is used to control access to a group of objects that are believed to be interrelated but often are not actually interrelated. This means that the control-objects are over inclusive and lock more than the required objects. This results in increased thread blocking and thus reduced performance.
It would be advantageous to monitor which objects in the object collection are actually interrelated and thus use each control object to limit access to the minimal group of the interrelated objects.